package lc.排序算法;

import java.util.Arrays;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/16
 */
public class quickSort {


    public int[] sort(int[] arr) {

        int l = 0; // 找到大于piv 的下标
        int r = arr.length - 1; // 找到小于piv 的下标

        sort(arr, l, r);
        return arr;
    }

    private void sort(int[] arr, int left, int right) {
        if (left >= right)
            return;
       int x = arr[left], i = left - 1, j = right + 1;
       while (i < j) {
           do i++; while(arr[i] < x);
           do j--; while(arr[j] > x);
           if (i < j) {
               int t = arr[i];
               arr[i] = arr[j];
               arr[j] = t;
           }

       }
       sort(arr,left,j);
       sort(arr,j + 1,right);
    }

    public static void main(String[] args) {

        quickSort q = new quickSort();

        int[] a = {1,45,73,7,3676,7,234,2,34,78,54,24};
        q.sort(a);
        System.out.println(Arrays.toString(a));
    }

}
